// https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

// 算法思路总结：
// 1. 使用滑动窗口技巧（双指针）维护无重复字符子串
// 2. right指针扩展窗口，记录字符出现次数
// 3. 当出现重复字符时，left指针收缩窗口直到重复消除
// 4. 在扩展过程中记录最大窗口长度
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <string>
#include <unordered_map>

class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        int ret = 0, n = s.size();
        unordered_map<char, int> up;

        for (int l = 0, r = 0 ; r < n ; r++)
        {
            up[s[r]]++;
            while (up[s[r]] > 1)
            {
                up[s[l]]--;
                l++;
            }
            ret = max(ret, r - l + 1);
        }
        return ret;
    }
};

int main()
{
    string s1 = "abcabcbb";
    string s2 = "bbbbb";

    Solution sol;
    cout << sol.lengthOfLongestSubstring(s1) << endl;
    cout << sol.lengthOfLongestSubstring(s2) << endl;

    return 0;
}